﻿#define _CRT_SECURE_NO_WARNINGS 1

//DP41 【模板】01背包
#include <iostream>
#include<cstring>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
//int dp[N][N];
int dp[N];

int main()
{
    // // 读⼊数据
    // cin >> n >> V;
    // for(int i = 1; i <= n; ++i)
    //     cin >> v[i] >> w[i];

    // // 解决第一问
    // for(int i = 1; i <= n; ++i)
    //     for(int j = 1; j <= V; ++j)
    //     {
    //         dp[i][j] = dp[i - 1][j];
    //         if(j >= v[i])
    //             dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
    //     }
    // cout<<dp[n][V]<<endl;

    // // 解决第二问
    // memset(dp,0,sizeof dp);
    // for(int j = 1; j <= V; ++j)
    //     dp[0][j] = -1;
    // for(int i = 1; i <= n; ++i)
    //     for(int j = 1; j <= V; ++j)
    //     {
    //         dp[i][j] = dp[i - 1][j];
    //         if(j >= v[i] && dp[i - 1][j - v[i]] != -1)
    //             dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
    //     }
    // cout<<(dp[n][V] == -1 ? 0 : dp[n][V])<<endl;


    //优化

    // 读⼊数据
    cin >> n >> V;
    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i];

    // 解决第一问
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= v[i]; --j)//修改遍历顺序,并且这里第一次遇到j < v[i]情况,后面就不需要考虑了
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << dp[V] << endl;

    // 解决第二问
    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; ++j)
        dp[j] = -1;
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= v[i]; --j)//修改遍历顺序
        {
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;


    return 0;
}

